CF480E Parking Lot

显然，如果每次删一个点，答案可能会减小，而且你还不知道在哪里减小的...

所以我们反向思考，如果每次加一个点，那么答案肯定是不减的，而且如果答案变大，新矩阵一定包含该点。

$up[i][j]$表示以$(i,j)$为起点出发向上能到达的 $'.~'$ 的个数。（遇到 $'X~'$ 停止）

$down[i][j]$表示以$(i,j)$为起点出发向下能到达的 $'.~'$ 的个数。（遇到 $'X~'$ 停止）

$up,down$都可以预处理，同时，我们也能用$dp$算出在所有点都无法选时（最后状态）的答案，记为$Ans$，不知道的看一下这道题：P1387 最大正方形。

设当前加入的点为$(x,y)$,首先，我们可以暴力更新$up,down$,我们只需要知道当前区间最小的$up+down-1$，如果$Ans$小于它，就将$Ans+1$ , 同时向两旁扩展一格（边长加1）显然我们可以用线段树维护。不用担心两旁遇到障碍的情况 , 这时的$up，down$都为$0$,无法对答案造成影响。

注意这里的线段树每次加点都要重建（$up,down$在变）。

#include <cstdio>
#include <iostream>
using namespace std;
#define ls x << 1
#define rs x << 1 | 1
#define INF 0x3f3f3f3f

const int MAXN = 2000;
int n , m , k , Minu , Mind , Map[ MAXN + 5 ][ MAXN + 5 ];
int up[ MAXN + 5 ][ MAXN + 5 ] , down[ MAXN + 5 ][ MAXN + 5 ];
struct node{
	int x , y , Ans;
}q[ MAXN + 5 ];

struct Point{
	int l , r , minu , mind;
};
struct Segment_Tree{
	Point Tree[ 4 * MAXN + 5 ];
	
	void Pushup( int x ) {
		Tree[ x ].minu = min( Tree[ ls ].minu , Tree[ rs ].minu );
		Tree[ x ].mind = min( Tree[ ls ].mind , Tree[ rs ].mind );
	}
	void Build( int dex , int x , int l , int r ) {
		Tree[ x ].l = l , Tree[ x ].r = r;
		if( l == r ) {
			Tree[ x ].minu = up[ dex ][ l ];
			Tree[ x ].mind = down[ dex ][ l ];
			return;
		}
		int Mid = ( l + r ) / 2;
		Build( dex , ls , l , Mid );
		Build( dex , rs , Mid + 1 , r );
		Pushup( x );
	}
	void Find( int x , int l , int r ) {
		if( r < Tree[ x ].l || Tree[ x ].r < l )
			return;
		if( l <= Tree[ x ].l && Tree[ x ].r <= r ) {
			Minu = min( Minu , Tree[ x ].minu );
			Mind = min( Mind , Tree[ x ].mind );
			return;
		}
		Find( ls , l , r );
		Find( rs , l , r );
	}
}Tree;

int dp[ MAXN + 5 ][ MAXN + 5 ];
void Dp( ) {
	for( int i = 1 ; i <= n ; i ++ )
		for( int j = 1 ; j <= m ; j ++ )
			if( Map[ i ][ j ] ) {
				dp[ i ][ j ] = min( dp[ i - 1 ][ j - 1 ] , min( dp[ i ][ j - 1 ] , dp[ i - 1 ][ j ] ) ) + 1;
				q[ k ].Ans = max( q[ k ].Ans , dp[ i ][ j ] );
			}
}

bool check( int x , int row ) {
	if( x > n || x > m ) return 0;
	for( int i = max( 1 , row - x + 1 ) ; i <= m - x + 1 ; i ++ ) {
		Minu = Mind = INF; Tree.Find( 1 , i , i + x - 1 );
		if( Minu + Mind - 1 >= x ) return 1;
	}
	return 0;
}

char s;
int main( ) {
	scanf("%d %d %d",&n,&m,&k);
	for( int i = 1 ; i <= n ; i ++ ) {
		getchar( );
		for( int j = 1 ; j <= m ; j ++ ) {
			scanf("%c",&s);
			Map[ i ][ j ] = ( s == '.' );
		}
	}
	for( int i = 1 ; i <= k ; i ++ ) {
		scanf("%d %d",&q[ i ].x,&q[ i ].y);
		Map[ q[ i ].x ][ q[ i ].y ] = 0;
		q[ i ].Ans = 0;
	}
	
	for( int i = 1 ; i <= n ; i ++ )
		for( int j = 1 ; j <= m ; j ++ )
			up[ i ][ j ] = Map[ i ][ j ] ? up[ i - 1 ][ j ] + 1 : 0;
	for( int i = n ; i >= 1 ; i -- )
		for( int j = 1 ; j <= m ; j ++ )
			down[ i ][ j ] = Map[ i ][ j ] ? down[ i + 1 ][ j ] + 1 : 0;
	Dp( );
	int Ans = q[ k ].Ans;
	for( int i = k ; i >= 1 ; i -- ) {
		int x = q[ i ].x , y = q[ i ].y; q[ i ].Ans = Ans;
		Map[ x ][ y ] = 1;
		
		up[ x ][ y ] = up[ x - 1 ][ y ] + 1;
		for( int t = x + 1 ; t <= n && Map[ t ][ y ] ; t ++ )
			up[ t ][ y ] += up[ x ][ y ];
		down[ x ][ y ] = down[ x + 1 ][ y ] + 1;
		for( int t = x - 1 ; t >= 1 && Map[ t ][ y ] ; t -- )
			down[ t ][ y ] += down[ x ][ y ];
		Tree.Build( x , 1 , 1 , m );
		while( check( Ans + 1 , y ) ) Ans ++;
	}
	for( int i = 1 ; i <= k ; i ++ )
		printf("%d\n",q[ i ].Ans);
	return 0;
}